Dear students, welcome to the first lecture of Secure Multi-Party Computation.

So we are beginning this lecture in general by creating the necessary foundation where

we cover all of the topics that you will need in order to understand how can we actually

construct a secure two-party computation protocol.

So in this lecture we will start with a very basic notion of algorithms and you will say

oh come on that's easy we had this before sure.

We will have randomized algorithm no dark magic here right we had them in crypto as

well under an introductory class but we will also discuss algorithms that get an advice.

So what is that?

Well these are algorithms that get an additional input this is the magic advice and the point

here is that this advice might be hard to to compute right so you can really think about

it in the following way that you have an algorithm that runs unbounded for a certain time and

in this time he computes the advice and after that you are essentially running the algorithm

with this advice.

So since this is an unrealistic assumption in general we will not assume that we have

such an algorithm in order to construct something but we will actually show that our protocols

are even secure against these powerful adversaries.

Furthermore we will also introduce the notion of circuits so this is a basic computation

model where you're not running an algorithm but you can express the algorithm in terms

of a circuit that has input wires certain gates where the computation is performed and

the output wires then return the result of the computation.

Furthermore we will also revisit the notion of one-way functions.

In this class we will be a little bit more formal and we need to specify where actually

the input is coming from.

So let me be a bit more precise here.

As you remember one-way function is a function that is easy to compute so you can compute

the result in polynomial time but it's hard to invert meaning that we don't have or we

believe that there is no efficient adversary that can go back and compute a valid preimage.

So here we will define this a little bit more formal.

In the introductory class we only look at algorithms or basically at one-way functions

where we could sample from the domain of uniform strings but in general that must not be the

case right.

So it might be that the one-way function only works for a very specific type of a domain

and we will formalize this as well.

So in each of these lectures I want to give you a short overview like I did this now such

that you understand where we are and where we are heading at.

In case something is not clear or confusing then please use the forum and ask questions.

It will help us to understand whether the videos are actually useful.

Better let them be useful.

And if not then please give us the feedback such that we can actually support you in understanding

this stuff.

Thank you very much and enjoy this lecture.

Preliminaries We start by defining the security parameter

which is lambda and in general we will provide lambda encoded in unary, so 1 to the lambda,

to all algorithms.

This is to make sure that the algorithm runs in polynomial time in their input length.

In general we omit this parameter in order to reduce the number of arguments that an

algorithm gets and to keep the notation as simple as possible.

We will now define algorithms and the different types of algorithms that we are considering.

The first type is the standard algorithm which basically gets an input and performs some